// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-21 16:22
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.typicalArrays;

public class typicalArrays_ {
    public int specialArray(int[] nums) {
        // 特殊数组的特征值如果存在最小为1最大为数组长度
        // 可以根据二分法进行查找
        int left = 1;
        int right = nums.length;
        int mid = 0;
        while (right > left) {
            mid = (right + left) >> 1;
            int tmp = ifSpecialNum(nums, mid);
            if (tmp > 0) {
                left = mid + 1;
            } else if (tmp < 0) {
                right = mid;
            } else {
                return mid;
            }
        }
        if (right == left) {
            return ifSpecialNum(nums, right) == 0 ? right : -1;
        }
        return -1;
    }

    public int ifSpecialNum(int[] nums, int k) {
        // to predicate the number k if the special number of th nums Arrays
        // if f is bigger than k means that k can be bigger
        // if f is smaller than k means that k can be smaller
        int f = 0;
        for (int num : nums) {
            if (num >= k) {
                ++f;
            }
        }
        return Integer.compare(f, k);
    }
}
